# 77/100 贪心算法-买卖股票的最佳时机
# leetcode第121题: https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/?envType=study-plan-v2&envId=top-100-liked
# Date: 2024/12/25
"""贪心算法
贪心算法一般没有一个固定的套路，但是它的边界是：可以通过局部最优的叠加来获得全局最优的结果
这不同于动态规划，动态规划的要义是通过牺牲局部来获取全局最优的方法
"""
from leetcode.test import test_function as tf
import json


def maxProfit(prices: list[int]) -> int:
    """最简单的方法，但是超时，单次计算超过41s"""
    n, res = len(prices), 0
    for i in range(n):
        for j in range(i + 1, n):
            res = max(res, prices[j] - prices[i])
    return res


def maxProfit_greed(prices: list[int]) -> int:
    """在python中如果进行多值比较可以使用max或者min函数，这样几可以保证代码的可读性，也不影响计算效率。
    如果是两值比较，且追求计算效率的情况下可以使用下面的通过大小判断来赋值的方法。"""
    profit = 0
    min_price = float('inf')  # 无穷大
    for price in prices:
        if price < min_price:
            min_price = price
        if price - min_price > profit:
            profit = price - min_price
    return profit


if __name__ == '__main__':
    with open("../data/n_greed1_lc121.data", "r") as file:
        jstr = file.readline().strip()
        jo = json.loads(jstr)
    inp = [{"prices": [7, 1, 5, 3, 6, 4]}, {"prices": [7, 6, 4, 3, 1]}, {"prices": jo['prices']}]
    out = [5, 0, 3]

    # tf(maxProfit, inp, out)
    tf(maxProfit_greed, inp, out)
